---
title: "L2-007 家庭房产"
created: 2025-11-28
tags:
  - 算法
---

# L2-007 家庭房产

## 题目 [L2-007 家庭房产](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805068539215872&page=1)

![[image-75953696.png]]

## 思路分析

并查集

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

// 宏定义及别名简化代码

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

// 定义四个方向（上下左右），可用于图遍历（虽然这里没用到）

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

// 预留但当前未用的数据结构

priority_queue<int> pq;

multimap<int,int> mp;

const int MAXN=10010; // 最大编号范围

// 并查集结构体

struct DSU{

	vector<int> parent;

	// 初始化，每个编号自成一个集合

	DSU(int n){

		parent.resize(n+1);

		for(int i=0;i<=n;i++){

			parent[i]=i;

		}

	}

	// 查找根节点 + 路径压缩

	int find(int x){

		if(parent[x]!=x)	parent[x]=find(parent[x]);

		return parent[x];

	}

	// 合并两个集合

	void unite(int x,int y){

		int fx=find(x);

		int fy=find(y);

		if(fx!=fy){

			parent[fx]=fy;

		}

	}

	// 判断两个节点是否属于同一集合

	bool connected(int x,int y){

		return find(x)==find(y);

	}

};

// 家庭结构体，用于储存每个家庭的信息

struct Family{

	int id;   // 家庭成员中最小编号

	int count; // 家庭人口数

	double totalEstate; // 房产总数

	double totalArea; // 总面积

	Family(int id = 0, int c = 0, double te = 0, double ta = 0)

        : id(id), count(c), totalEstate(te), totalArea(ta) {}

	// 排序方式：人均面积降序，若相同则编号升序

	bool operator<(const Family& other) const{

		if(fabs(totalArea/count - other.totalArea/other.count)>1e-6)

			return totalArea/count > other.totalArea/other.count;

		return id<other.id;

	}

};

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n;cin>>n;

	DSU dsu(MAXN); // 初始化并查集

	// 存储每个编号是否存在

	vector<int> exist(MAXN,0);

	// 储存每个编号的房产套数和面积

	vector<double> estate(MAXN,0),area(MAXN,0);

	vector<int> people; // 所有涉及过的人

	// 读入每组数据，建立家庭成员之间的联系

	for(int i=0;i<n;i++){

		int id,fa,mo,k;

		cin>>id>>fa>>mo>>k;

		exist[id]=1;

		people.push_back(id);

		// 父亲并入集合

		if(fa!=-1){

			dsu.unite(id,fa);

			exist[fa]=1;

			people.push_back(fa);

		}

		// 母亲并入集合

		if(mo!=-1){

			dsu.unite(id,mo);

			exist[mo]=1;

			people.push_back(mo);

		}

		// 子女并入集合

		for(int j=0;j<k;j++){

			int child;cin>>child;

			dsu.unite(id,child);

			exist[child]=1;

			people.push_back(child);

		}

		// 输入该人拥有的房产信息

		int sets; double ar;

		cin>>sets>>ar;

		estate[id]+=sets;

		area[id]+=ar;

	}

	map<int,Family> families; // 用于按家庭根节点记录汇总信息

	map<int,int> min_id; // 每个集合中最小编号的成员

	// 遍历所有出现过的编号，统计每个家庭的信息

	for(int i=0;i<MAXN;i++){

		if(!exist[i])	continue;

		int root = dsu.find(i); // 找出集合代表

		// 若首次遇到该集合

		if(families.find(root)==families.end()){

			families[root]=Family(i,1,estate[i],area[i]);

			min_id[root]=i;

		}else{

			// 累加集合中的其他成员信息

			families[root].count++;

			families[root].totalEstate+=estate[i];

			families[root].totalArea += area[i];

            min_id[root] = min(min_id[root], i); // 保证最小编号正确

		}

	}

	// 把map结构转换为vector并排序，方便输出

    vector<Family> res;

    for (auto &it : families) {

        int id = min_id[it.first];

        auto fam = it.second;

        fam.id = id;

        res.push_back(fam);

    }

    sort(res.begin(), res.end()); // 按人均面积排序

    // 输出家庭数量

    printf("%d\n",res.size());

    // 输出每个家庭的信息

    for (auto &f : res) {

        // 编号补零至4位，保留三位小数

        printf("%04d %d %.3lf %.3lf\n", f.id, f.count,

               f.totalEstate / f.count, f.totalArea / f.count);

    }

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[性质|性质]] 🏠 [[00-天梯赛]] ➡️ [[L2-008 最长对称子串|L2-008 最长对称子串]]